<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">Homogeneous kernel map </div>  </div>
</div>
<div class="contents">
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Andrea Vedaldi</dd></dl>
<p><a class="el" href="homkermap_8h.html">homkermap.h</a> implements the homogeneous kernel maps introduced in <a class="el" href="citelist.html#CITEREF_vedaldi10efficient">[13]</a> , <a class="el" href="citelist.html#CITEREF_vedaldi11efficient">[14]</a> . Such maps are efficient linear representations of popular kernels such as the intersection, <img class="formulaInl" alt="$ \chij^2 $" src="form_61.png"/>, and Jensen-Shannon ones.</p>
<ul>
<li><a class="el" href="homkermap.html#homkermap-overview">Overview</a><ul>
<li><a class="el" href="homkermap.html#homkermap-overview-negative">Extension to the negative reals</a></li>
<li><a class="el" href="homkermap.html#homkermap-overview-homogeneity">Homogeneity order</a></li>
<li><a class="el" href="homkermap.html#homkermap-overview-window">Windowing and period</a></li>
</ul>
</li>
<li><a class="el" href="homkermap.html#homkermap-usage">Usage</a></li>
<li><a class="el" href="homkermap.html#homkermap-tech">Technical details</a></li>
</ul>
<h2><a class="anchor" id="homkermap-overview"></a>
Overview</h2>
<p>The <em>homogeneous kernel map</em> is a finite dimensional linear approximation of homgeneous kernels, including the intersection, <img class="formulaInl" alt="$ \chi^2 $" src="form_62.png"/>, and Jensen-Shannon kernels. These kernels are ffrequently used in computer vision applications because they are particular suitable for data in the format of histograms, which encompasses many visual descriptors used.</p>
<p>Let <img class="formulaInl" alt="$ x,y \in \mathbb{R}_+ $" src="form_63.png"/> be non-negative scalars and let <img class="formulaInl" alt="$ k(x,y) \in \mathbb{R} $" src="form_64.png"/> be an homogeneous kernel such as the <img class="formulaInl" alt="$ \chi^2 $" src="form_62.png"/> and or the intersection ones:</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ k_{\mathrm{inters}}(x,y) = \min\{x, y\}, \quad k_{\chi^2}(x,y) = 2 \frac{(x - y)^2}{x+y}. \]" src="form_65.png"/>
</p>
<p>For vectorial data <img class="formulaInl" alt="$ \mathbf{x},\mathbf{y} \in \mathbb{R}_+^d $" src="form_66.png"/>, the homogeneous kernels in an <em>additive combination</em> <img class="formulaInl" alt="$ K(\mathbf{x},\mathbf{y}) = \sum_{i=1}^d k(x_i,y_i) $" src="form_67.png"/>.</p>
<p>The <em>homogeneous kernel map</em> of order <img class="formulaInl" alt="$ n $" src="form_68.png"/> is a vectorial function <img class="formulaInl" alt="$ \Psi(x) \in \mathbb{R}^{2n+1} $" src="form_69.png"/> such that, for any choice of <img class="formulaInl" alt="$ x, y \in \mathbb{R}_+ $" src="form_70.png"/>, one has</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ k(x,y) \approx \langle \Psi(x), \Psi(y) \rangle. \]" src="form_71.png"/>
</p>
<p>Given the feature map for the scalar case, the corresponding feature map <img class="formulaInl" alt="$ \Psi(\mathbf{x}) $" src="form_72.png"/> for the vectorial case is obtained by stacking <img class="formulaInl" alt="$ [\Psi(x_1), \dots, \Psi(x_n)] $" src="form_73.png"/>. Note that the combined feature <img class="formulaInl" alt="$ \Psi(\mathbf{x}) $" src="form_72.png"/> has dimension <img class="formulaInl" alt="$ d(2n+1) $" src="form_74.png"/>.</p>
<p>Using linear analysis tools (e.g. a linear support vector machine) on top of dataset that has been encoded by the homogeneous kernel map is therefore approximately equivalent to using a method based on the corresponding non-linear kernel.</p>
<h3><a class="anchor" id="homkermap-overview-negative"></a>
Extension to the negative reals</h3>
<p>Any positive (semi-)definite kernel <img class="formulaInl" alt="$ k(x,y) $" src="form_75.png"/> defined on the non-negative reals <img class="formulaInl" alt="$ x,y \in \mathbb{R}_+ $" src="form_63.png"/> can be extended to the entiere real line by using the definition:</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ k_\pm(x,y) = \operatorname{sign}(x) \operatorname{sign}(y) k(|x|,|y|). \]" src="form_76.png"/>
</p>
<p>The homogeneous kernel map implements this extension by defining <img class="formulaInl" alt="$ \Psi_\pm(x) = \operatorname{sign}(x) \Psi(|x|) $" src="form_77.png"/>. Note that other extensions are possible, such as</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ k_\pm(x,y) = H(xy) \operatorname{sign}(y) k(|x|,|y|) \]" src="form_78.png"/>
</p>
<p>where <img class="formulaInl" alt="$ H $" src="form_79.png"/> is the Heavyside function, but may require higher dimensional feature maps.</p>
<h3><a class="anchor" id="homkermap-overview-homogeneity"></a>
Homogeneity order</h3>
<p>Any (1-)homogeneous kernel <img class="formulaInl" alt="$ k_1(x,y) $" src="form_80.png"/> can be extended to a so called gamma-homgeneous kernel <img class="formulaInl" alt="$ k_\gamma(x,y) $" src="form_81.png"/> by the definition</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ k_\gamma(x,y) = (xy)^{\frac{\gamma}{2}} \frac{k_1(x,y)}{\sqrt{xy}} \]" src="form_82.png"/>
</p>
<p>Smaller value of <img class="formulaInl" alt="$ \gamma $" src="form_83.png"/> enhance the kernel non-linearity and are sometimes beneficial in applications (see [1,2] for details).</p>
<h3><a class="anchor" id="homkermap-overview-window"></a>
Windowing and period</h3>
<p>This section discusses aspects of the homogeneous kernel map which are more technical and may be skipped. The homogeneous kernel map approximation is based on periodicizing the kernel; given the kernel signature</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \Kappa(\lambda) = k(e^{\frac{\lambda}{2}}, e^{-\frac{\lambda}{2}}) \]" src="form_84.png"/>
</p>
<p>the homogeneous kerne map is a feature map for the windowed and periodicized kernel whose signature is given by</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \hat{\mathcal{K}}(\lambda) = \sum_{i=-\infty}^{+\infty} \mathcal{K}(\lambda + k \Lambda) W(\lambda + k \Lambda) \]" src="form_85.png"/>
</p>
<p>where <img class="formulaInl" alt="$ W(\lambda) $" src="form_86.png"/> is a windowing function and <img class="formulaInl" alt="$ \Lambda $" src="form_87.png"/> is the period. This implementation of the homogeneous kernel map supports the use of a <em>uniform window</em> ( <img class="formulaInl" alt="$ W(\lambda) = 1 $" src="form_88.png"/>) or of a <em>rectangular window</em> ( <img class="formulaInl" alt="$ W(\lambda) = \operatorname{rect}(\lambda/\Lambda) $" src="form_89.png"/>). Note that <img class="formulaInl" alt="$ \lambda = \log(y/x) $" src="form_90.png"/> is equal to the logarithmic ratio of the arguments of the kernel. Empirically, the rectangular window seems to have a slight edge in applications.</p>
<h2><a class="anchor" id="homkermap-usage"></a>
Usage</h2>
<p>The homogeneous kernel map is implemented as an object of type <a class="el" href="structVlHomogeneousKernelMap.html" title="Homogeneous kernel map.">VlHomogeneousKernelMap</a>. To use thois object, first create an instance by <a class="el" href="homkermap_8h.html#a87e86a2981550ae60f565575c32966ea" title="Create a new homgeneous kernel map.">vl_homogeneouskernelmap_new</a>, then use <a class="el" href="homkermap_8h.html#aa46c3f8cfdf0f1334727c27c13e77608" title="Evaluate map.">vl_homogeneouskernelmap_evaluate_d</a> or <a class="el" href="homkermap_8h.html#a2ea4628d7a00b9543112fc4dd2d8f380" title="Evaluate map.">vl_homogeneouskernelmap_evaluate_f</a> (depdening on whether the data is <code>double</code> or <code>float</code>) to compute the feature map <img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/>. When done, dispose of the object by calling <a class="el" href="homkermap_8h.html#a9a059f792833cb10e62f5f476f99f0da" title="Delete a map object.">vl_homogeneouskernelmap_delete</a>.</p>
<p>The constructor <a class="el" href="homkermap_8h.html#a87e86a2981550ae60f565575c32966ea" title="Create a new homgeneous kernel map.">vl_homogeneouskernelmap_new</a> requires the kernel type <code>kernel</code> (see <a class="el" href="homkermap_8h.html#a13074dd7edec5d8c86dde5da80e8d8d8" title="Type of kernel.">VlHomogeneousKernelType</a>), the homogeneity order <code>gamma</code> (use one for the standard kernels), the approximation order <code>order</code> (usually order one is enough), the period <em>period</em> (use a negative value to use the default period), and a window type <code>window</code> (use <a class="el" href="homkermap_8h.html#a35a05da3e1eb781a6fa997ec9be69a62a83070b8b6be773c61bc3f19fc4583053">VlHomogeneousKernelMapWindowRectangular</a> if unsure). The approximation order trades off the quality and dimensionality of the approximation. The resulting feature map <img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/>, computed by <a class="el" href="homkermap_8h.html#aa46c3f8cfdf0f1334727c27c13e77608" title="Evaluate map.">vl_homogeneouskernelmap_evaluate_d</a> or <a class="el" href="homkermap_8h.html#a2ea4628d7a00b9543112fc4dd2d8f380" title="Evaluate map.">vl_homogeneouskernelmap_evaluate_f</a> , is <code>2*order+1</code> dimensional.</p>
<p>The code pre-computes the map <img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/> for efficient evaluation. The table spans values of <img class="formulaInl" alt="$ x $" src="form_92.png"/> in the range <img class="formulaInl" alt="$[2^{-20}, 2^{8}) $" src="form_93.png"/>. In particular, values smaller than <img class="formulaInl" alt="$ 2^{-20} $" src="form_94.png"/> are treated as zeroes (which result in a null feature).</p>
<h2><a class="anchor" id="homkermap-tech"></a>
Technical details</h2>
<p>The code uses the expressions given in <a class="el" href="citelist.html#CITEREF_vedaldi10efficient">[13]</a> , <a class="el" href="citelist.html#CITEREF_vedaldi11efficient">[14]</a> to compute in closed form the maps <img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/> for the suppoerted kernel types. For efficiency reasons, it tabulates <img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/> when the homogeneous kernel map object is created.</p>
<p>The interal table stores <img class="formulaInl" alt="$ \Psi(x) \in \mathbb{R}^{2n+1} $" src="form_69.png"/> for <img class="formulaInl" alt="$ x \geq 0 $" src="form_95.png"/> by sampling this variable. In particular, <code>x</code> is decomposed as </p>
<pre>
  x = mantissa * (2**exponent),
  minExponent &lt;= exponent &lt;= maxExponent,
  1 &lt;= matnissa &lt; 2.
</pre><p> Each octave is further subdivided in <code>numSubdivisions</code> sublevels.</p>
<p>When the map <img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/> is evaluated, <code>x</code> is decomposed back into exponent and mantissa, and the result is computed by bilinear interpolation from the appropriate table entries. </p>
</div></div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
